//98
import BTree from "./index.js";
function isValidBST(root) {
  let result = true;
  function travel(root) {
    if (!result) return null;
    if (root === null) {
      return null;
    }
    const leftRes = travel(root.left);
    const rightRes = travel(root.right);
    if (leftRes !== null && leftRes.max >= root.val) {
      result = false;
    }
    if (rightRes !== null && rightRes.min <= root.val) {
      result = false;
    }
    return {
      max: Math.max(
        root.val,
        leftRes ? leftRes.max : -Infinity,
        rightRes ? rightRes.max : -Infinity
      ),
      min: Math.min(
        root.val,
        leftRes ? leftRes.min : Infinity,
        rightRes ? rightRes.min : Infinity
      ),
    };
  }
  travel(root);
  return result;
}
const tree = new BTree([
  120, 70, 140, 50, 100, 130, 160, 20, 55, 75, 110, 119, 135, 150, 200,
]);
console.log(isValidBST(tree));

//自顶向下遍历要简洁很多
const helper = (root, lower, upper) => {
  if (root === null) {
    return true;
  }
  if (root.val <= lower || root.val >= upper) {
    return false;
  }
  return (
    helper(root.left, lower, root.val) && helper(root.right, root.val, upper)
  );
};
var isValidBST = function (root) {
  return helper(root, -Infinity, Infinity);
};
